package com.hgx.algorithm.base.sort;

import static com.hgx.algorithm.base.utils.ArraySortUtil.*;

/**
 * 冒泡排序
 * 时间复杂度：O(N^2)
 * 额外空间复杂度：O(1)
 * 稳定性：稳定
 */
public class BubbleSort {


    public static void main(String[] args) {
//        int[] arr = new int[]{2, 7, 5, 4, 38, 6, 9};
        int[] arr = generateRandomArray(20, 100);
        print(arr);
        sort(arr);
//        sort1(arr);
        print(arr);
    }

    //实现1
    public static void sort1(int[] arr) {

        if (arr == null || arr.length < 2) {
            return;
        }
        for (int e = arr.length - 1; e > 0; e--) {
            for (int i = 0; i < e; i++) {
                if (arr[i] > arr[i + 1]) {
                    swap(arr, i, i + 1);
                }
            }
        }
    }

    //实现2
    public static void sort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    swap(arr, i, j);
                }
            }
        }
    }
}
